package 十大排序;

import java.util.Arrays;

public class Sort {
    public static void main(String[] args) {
        int[] arr = {10,6,8,5,9};
        int[] q = quickSort2(arr, 0, arr.length-1);
        for (int i = 0; i < q.length-1; i++) {
            System.out.print(q[i]+",");
        }
        System.out.println(q[arr.length-1]);
    }

    private static int[] quickSort2(int[] arr, int start, int end) {

        int base = partition2(arr, start, end);

        if(base>start) {
            quickSort2(arr, start, base-1);
        }
        if(base<end) {
            quickSort2(arr, base+1, end);
        }
        return arr;
    }

    private static int partition2(int[] arr, int start, int end) {
        //基准为最左边
        int base = start;

        //左右指针
        int left = start;
        int right = end;


        while (left<right) {
            //每次循环，找到 左边第一个比基准大的，右边第一个比基准小的，然后交换，  直到 left = right后，将基准和right互换。
            while (arr[right]>=arr[base] && left<right) {
                right--;
            }

            while (arr[left]<=arr[base] && left<right) {
                left++;
            }

            if(left<right) {
                swap(arr, left, right);
            }
        }
        swap(arr, base, right);
        return right;
    }

    /**
     * 快速排序： 随机找一个基准，比基准大的放一边，比基准小的放另一边
     * 一个快排讲解比较清晰的链接 https://blog.csdn.net/shujuelin/article/details/82423852
     * @param
     * @return
     */
    private static int[] quickSort(int[] arr, int start, int end) {
        if (start < 0 || end >= arr.length || start > end) return null;

        //分区
        int smallIndex = partition(arr, start, end);
        if(smallIndex > start) {
            quickSort(arr, start, smallIndex-1);
        }
        if(smallIndex < end) {
            quickSort(arr, smallIndex+1, end);
        }
        return arr;
    }

    private static int partition(int[] arr, int start, int end) {
        //拿到一个随机索引
        int base = (int) (start + Math.random() * (end - start + 1));

        //设置准备返回的值
        int smallIndex = start - 1;
        //将base放在最后面
        swap(arr, base, end);

        for (int i = start; i <= end; i++) {
            if(arr[i] <= arr[end]) {
                //这两步看不太懂
                smallIndex++;
                if(i>smallIndex) {
                    swap(arr, i, smallIndex);
                }
            }

        }
        return smallIndex;
    }

    private static void swap(int[] arr, int base, int end) {
        int temp = arr[base];
        arr[base] = arr[end];
        arr[end] = temp;
    }

    /**
     * 归并排序：思路值得学习  分为左右两个数组，递归的对元素进行排序，知道数组不可拆分
     * @param arr
     */
    private static int[] mergeSort(int[] arr) {
        if (arr.length < 2) return arr;
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];

        //三个游标， index是最终数组的游标， l是左数组的游标， r是右数组的游标
        for (int index = 0, l = 0, r = 0; index < result.length; index++) {
            if (l >= left.length)   // l>= left.length  和 r>=right.length是当一个数组被遍历完了，数组越界的情况处理
                result[index] = right[r++];
            else if (r >= right.length)
                result[index] = left[l++];
            else if (left[l] > right[r])
                result[index] = right[r++];
            else
                result[index] = left[l++];
        }
        return result;
    }


    /**
     * 插入排序：从后往前，比较移动
     * @param arr
     */
    private static void insertSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            int index = i;
            int cur = arr[i+1];
            while (index>=0 && cur<arr[index]) {
                arr[index+1] = arr[index];
                index--;
            }
            arr[index+1] = cur;
        }
    }

    /**
     * 选择排序：每次选择最小的放到前面
     * @param arr
     */
    private static void chooseSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j]<arr[i]) {
                    minIndex = j;
                }
            }
            if(minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

    /**
     * 冒泡排序：每次将最小的放到最前面
     * @param arr
     */
    private static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j]<arr[i]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

//    1. 堆排序
//    什么是堆？
//    用数组组成的二叉树
//            从0开始
//    父节点的索引为i，  那么左右孩子分别为   2i+1  2i+2
//
//    大顶堆：  arr[i] >= arr[2i+1]   && arr[i] >= arr[2i+2]
//    小顶堆    arr[i] <= arr[2i+1]   && arr[i] <= arr[2i+2]

    /**
     * 升序大顶堆，降序小顶堆
     * 1. 从倒数第一个非叶子节点开始  arr.length/2-1, 构建大顶堆
     * 2. 将根节点和最后一个叶子节点交换，重新构建大顶堆
     * 3. 循环往复
     * @param arr
     */
    private static void heapSort(int[] arr) {
        int length = arr.length;

        for(int i= arr.length/2-1;i>=0;i--) {
            buildMaxHeap(arr, i, length);        //构建大顶堆
        }

        for (int i = arr.length-1; i >=0; i--) {
            swap(arr, 0, i);
            length--;
            buildMaxHeap(arr, 0, length);   // 这里从0开始，注意为什么?
        }
    }

    private static void buildMaxHeap(int[] arr, int i, int length) {
        int leftIndex = 2*i +1;
        int rightIndex = 2*i +2;
        int bigIndex = i;

        //找到根、左右，最大的，放到根部
        if(leftIndex<length && arr[leftIndex]>arr[bigIndex]) {
            bigIndex = leftIndex;
        }
        if(rightIndex<length && arr[rightIndex]>arr[bigIndex]) {
            bigIndex = rightIndex;
        }

        if(i != bigIndex) {
            swap(arr, i, bigIndex);

            //交换最大的和根后， 相当于根下移，此时需要重新构建 bigIndex为根的树为大顶堆
            /**
             *    4
             *   / \
             *   5 6
             *   4和6换了后， 需要比较4和 6的子节点的大小，进行下推
             */
            buildMaxHeap(arr, bigIndex, length);
        }
    }
}
